The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
Border Gateway Protocol (BGP) is an exterior gateway protocol (EGP) that is used to exchange routing information among network elements in the same or different networks. A network element is a device that is configured for managing, processing, and/or forwarding network traffic. (Examples of network elements include, but are not limited to, repeaters, bridges, switches, and routers.) In order to exchange BGP routing information, two network elements first establish a transport protocol session such as, for example, a Transmission Control Protocol (TCP) session or a Stream Control Transmission Protocol (SCTP) association. The BGP processes executing on the network elements then establish a BGP peering session by exchanging, over the transport protocol session, a series of BGP OPEN messages that define the parameters of the BGP session. After the BGP session is open, the BGP processes (referred to as BGP peers) exchange all of their routing information. Thereafter, only updates or changes to the routing information are exchanged, or advertised, between the BGP peers. The BGP peers maintain the exchanged routing information during the existence of the BGP session.
The routing information exchanged during a BGP session includes routes to address destinations in one or more networks. A route comprises an address prefix of the destination and attributes that describe the path to the destination. A BGP process stores the routes it receives from its BGP peers in a local Routing Information Bases (RIB). If a network element were configured to execute multiple BGP processes, typically each BGP process executing on the network element would manage its own local RIB. In a typical BGP process implementation, a local BGP RIB may include three distinct portions: (a) Adj-RIBs-In, which stores routes received from BGP peers or learned from other protocols, (b) Loc-RIB, which stores routes that the BGP process has selected by applying one or more route selection algorithms to the routes stored in Adj-RIBs-In, and (c) Adj-RIBs-Out, which stores routes that the BGP process has selected for advertisement to its BGP peers.
The routes that a BGP process stores in Adj-RIBs-In are typically received over a BGP session established with a BGP peer. The routes stored in Loc-RIB are selected from the routes in Adj-RIBs-In by applying one or more route selection algorithms. The routes selected by the BGP process and stored in the Loc-RIB usually represent the best paths to the routes' respective address destinations. Once the best route to a certain address destination is selected and stored in the Loc-RIB, the BGP process may advertise the route to its BGP peers by placing (or storing) the route in Adj-RIBs-Out.
In some network element architectures, some or all of the best routes stored in a BGP Loc-RIB are installed in a global RIB maintained at the network element. The global RIB includes routes that the network element receives over all of its route management protocols including, but not limited to, EGP protocols such as BGP, and Internal Gateway Protocols (IGP) such as Open Shortest Path First (OSPF) protocol, Interior Gateway Routing Protocol (IGRP), and Routing Information Protocol (RIP). Some or all of the routes in the global RIB are installed in one or more Forwarding Information Bases (FIBs) that are hosted at the network element. A FIB is a physical or logical table that stores routes used to forward network packets to the address destinations of the stored routes. A typical FIB stores only one route (the best route) for each address destination that is reachable through the network element that hosts the FIB. In a typical network element, a FIB is associated with a forwarding engine that is configured to receive network packets from other network elements and to forward these packets based on the routes installed in the FIB. A forwarding engine may comprise a set of hardware and/or software components capable of receiving and forwarding network traffic, and in different network element architectures the forwarding engine may be executing on a route processor or on a line card of the network element.
In a standard BGP implementation (such as, for example, a BGP implementation conforming to the BGP-4 standard defined in RFC1771 or to the MP-BGP standard defined in RCF2858), when the BGP session between two BGP peers is closed or lost for whatever reason, each BGP peer discards any routing information received from the other peer and removes any routes received from the other peer from its global RIB and its FIBs. Thus, when afterwards the two BGP peers re-establish a new BGP session, in order to provide forwarding capabilities on each other's routes, the two BGP peers need to go through the same time and resource consuming process of exchanging anew all of their routing information, running route selection algorithms, and installing the selected routes in their respective global RIBs and FIBs.
In order to reduce the negative effects of a BGP session loss, a Graceful Restart mechanism for BGP has been proposed, the latest version of which was published by the IETF in December 2004 as draft-ietf-idr-restart-10.txt. The BGP Graceful Restart mechanism provides a new BGP capability, termed “Graceful Restart Capability”, which is advertised by a BGP process during the set up of a BGP session with a BGP peer. A BGP process that advertises a Graceful Restart capability to its BGP peer guarantees that, in the event the BGP peer restarts, the network element executing the BGP process is capable of preserving the routes in its FIB received from the BGP peer and is capable of forwarding packets on these routes. The BGP process that restarts is commonly referred to as the restarting BGP peer; the BGP process that has established a BGP session to a restarting BGP peer is commonly referred to as the receiving BGP peer. According to the BGP Graceful Restart mechanism, when the receiving BGP peer detects that the restarting BGP peer has restarted, the receiving BGP peer marks as “stale” the routes in its Loc-RIB that are received from the restarting BGP peer. However, no routes are removed from the global RIB or from the FIBs that are hosted by the network element executing the receiving BGP peer, and forwarding of network packets on any “stale” routes is not affected. (As referred to herein, a “stale” route is a route that has been received over a BGP session that has since become unavailable.) In this way, the network element executing the receiving BGP peer preserves its forwarding state and guarantees non-interrupted forwarding service on routes received from the restarting BGP peer.
The BGP Graceful Restart mechanism has several disadvantages. One disadvantage is that the BGP Graceful Restart mechanism only guarantees forwarding of network packets for a network element executing the receiving BGP peer. The BGP Graceful Restart mechanism does not provide, or require, that a network element executing a restarting BGP peer preserve its forwarding state and guarantee the forwarding of network packets on routes received from a receiving BGP peer. In some network element architectures, this problem is addressed by providing the network element with one or more standby forwarding engines. When a BGP process executing at such network element restarts for whatever reason, the network element switches the forwarding state of its active forwarding engine to a standby forwarding engine (by, for example, installing all routes from the active FIB into the standby FIB). However, network elements supporting one or more standby forwarding engines are generally more expensive and more costly to maintain.
Another disadvantage of the BGP Graceful Restart mechanism is that it presumes the restarting BGP peer would always restart as a result of the loss of the transport protocol session over which a BGP session to the receiving BGP peer is established. For example, the BGP Graceful Restart mechanism is only applicable to a receiving BGP peer that has established a BGP session to a restarting BGP peer that is executing in a monolithic Operating System (OS). In a monolithic OS, a BGP process cannot continue executing when the transport protocol process, over which a BGP session is established, becomes unavailable since the transport protocol process is built into the kernel of the OS. When the transport protocol process crashes (which is one of the common causes of BGP process restarts), the entire OS restarts which in turn causes the BGP process to restart. Thus, the BGP process cannot continue executing when the transport protocol process crashes or becomes otherwise unavailable.
In a multi-process OS, however, the different OS processes execute over a microkernel, and each process is capable of restarting individually and separately from the microkernel and the other processes in the OS. (An example of a multi-process OS is the modular IOS provided by Cisco Systems, Inc.) In a multi-process OS, a transport protocol process, such as a TCP process, is capable of restarting without causing a BGP process executing in the OS to restart. However, when the BGP process detects that the BGP sessions it has established to its BGP peers have been lost (because of the transport protocol process restart), the BGP process must remove from the global RIB and from the FIB the routes it has received over these BGP sessions, even though the BGP process has not restarted and regardless of whether the BGP process has been configured to implement the BGP Graceful Restart mechanism. Removal of the routes from the global RIB and the FIB, however, causes an interruption in the forwarding service provided by the network element running the multi-process OS because network packets cannot be forwarded over the routes that are removed from the FIB.
Based on the foregoing, there is a clear need for graceful restart techniques in multi-process operating systems that overcome the disadvantages described above and that facilitate non-interrupted forwarding service across transport protocol process restarts.